#ifndef NEWLIST_H_
#define NEWLIST_H_

#include <cstddef>
#include <cassert>
#include <exception>

class ListException: public std::exception{};

class EmptyListException: public ListException{};
class NonMatchingListException: public ListException{};
class NoElementException: public ListException{};

template <class T>
class List {
	struct Node {
		T* element;
		Node* next;
		Node* previous;

		Node(const T& element) :
			element(new T(element)), next(NULL), previous(NULL) { };
		// especially for creating dummy node:
		Node() :
			element(NULL), next(NULL), previous(NULL) { };
		~Node() {
			delete element;
		}

		/* Copy C'tor and operator= were not implemented since there is no
		 * immediate / obvious interpretation to their action when it comes to
		 * a node.
		 */
	};

	Node* const dummyHead;
	Node* const dummyTail;
	int size;

public:
	class Iterator;
	class ConstIterator;

	class Iterator {
		List* list;
		Node* current;
		friend class List;
		friend class ConstIterator;
		Iterator(List* list, Node* node = NULL);
		void validateListMatch(const List<T>* otherList) const;
	public:
		T& operator*();
		Iterator& operator++();
		Iterator operator++(int);
		Iterator& operator--();
		Iterator operator--(int);
		bool operator==(const typename List<T>::Iterator& iterator);
		bool operator!=(const typename List<T>::Iterator& iterator);
		bool operator==(const typename List<T>::ConstIterator& iterator);
		bool operator!=(const typename List<T>::ConstIterator& iterator);
		void removeFromList();
	};
	class ConstIterator {
		const List* list;
		Node* current;
		friend class List;
		ConstIterator(const List* list, Node* node = NULL);
	public:
		ConstIterator(const Iterator& iterator);
		const T& operator*();
		ConstIterator& operator++();
		ConstIterator operator++(int);
		ConstIterator& operator--();
		ConstIterator operator--(int);
		bool operator==(const typename List<T>::ConstIterator& iterator);
		bool operator!=(const typename List<T>::ConstIterator& iterator);
	};

	List();
	~List();
	List(const List& list); /* Copy C'tor */
	List& operator=(const List& list);
	bool operator==(const List<T>& list) const;
	bool operator!=(const List<T>& list) const;
	Iterator begin();
	ConstIterator begin() const;
	Iterator end();
	ConstIterator end() const;
	Iterator rbegin();
	ConstIterator rbegin() const;
	Iterator rend();
	ConstIterator rend() const;
	/* Inserts element to the beginning of the list. */
	void insertFirst(const T& element);
	void remove(const Iterator& iterator);
	template <class Predicate>
	Iterator find(const Predicate predicate);
	template <class Predicate>
	ConstIterator find(const Predicate predicate) const;
private:
	void clear();
	void copyFrom(const List& sourceList);
};

/* List member methods */

template<class T>
List<T>::List() : dummyHead(new Node), dummyTail(new Node), size(0) {
	dummyHead->next = dummyTail;
	dummyTail->previous= dummyHead;
}

template<class T>
List<T>::~List() {
	clear();
	delete dummyHead;
	delete dummyTail;
}

template<class T>
List<T>::List(const List<T>& list) : dummyHead(new Node),
dummyTail(new Node), size(0) {
	/* Initializing dummy nodes so that clear method, which will take affect
	 * later, will perform well.
	 */
	dummyHead->next = dummyTail;
	dummyTail->previous= dummyHead;

	// using operator= to implement the copy c'tor
	*this = list;
}

template<class T>
List<T>& List<T>::operator=(const List<T>& list) {
	// Dealing with assignment of a list to itself
	if (this == &list) {
		return *this;
	}

	List newTempList;
	// Copying list elements to a temporary list
	newTempList.copyFrom(list);
	// Clear our list
	clear();
	/* Wiring the temporary list nodes to our list. This is all done for
	 * allocating the new nodes for our list before we remove its old nodes.
	 */
	size = newTempList.size;
	dummyHead->next = newTempList.dummyHead->next;
	dummyHead->next->previous = dummyHead;
	dummyTail->previous = newTempList.dummyTail->previous;
	dummyTail->previous->next = dummyTail;

	newTempList.dummyHead->next = newTempList.dummyTail;
	newTempList.dummyTail->previous = newTempList.dummyHead;

	return *this;
}

template<class T>
void List<T>::remove(const typename List<T>::Iterator& iterator) {
	iterator.validateListMatch(this);

	if ((dummyHead == iterator.current) || (dummyTail == iterator.current)) {
		throw NoElementException();
	}

	Node* previousNode = iterator.current->previous;
	Node* nextNode = iterator.current->next;
	previousNode->next = nextNode;
	nextNode->previous = previousNode;

	delete iterator.current;
	--size;
}

/* Returns an iterator to the first element of list that yields true for the
 * predicate. If no element yields true - returns an iterator to the end of the
 * list.
 */
template<class T> template <class Predicate>
typename List<T>::Iterator List<T>::find(const Predicate predicate) {
	for (List<T>::Iterator elementIterator = begin(); elementIterator != end();
			++elementIterator) {
		if (predicate(*elementIterator)) {
			return elementIterator;
		}
	}
	return end();
}

template<class T> template <class Predicate>
typename List<T>::ConstIterator List<T>::find(const Predicate predicate) const {
	for (List<T>::ConstIterator elementIterator = begin();
			elementIterator != end(); ++elementIterator) {
		if (predicate(*elementIterator)) {
			return elementIterator;
		}
	}
	return end();
}

template<class T>
List<T>::Iterator::Iterator(
		List<T>* list, typename List<T>::Node * node) : list(list),
		current(node) {}

template<class T>
List<T>::ConstIterator::ConstIterator(
		const List* list, typename List<T>::Node* node) : list(list),
		current(node) {}

template<class T>
typename List<T>::Iterator List<T>::begin() {
	return Iterator(this, dummyHead->next);
}

template<class T>
typename List<T>::ConstIterator List<T>::begin() const {
	return ConstIterator(this, dummyHead->next);
}

template<class T>
typename List<T>::Iterator List<T>::end() {
	return Iterator(this, dummyTail);
}

template<class T>
typename List<T>::ConstIterator List<T>::end() const {
	return ConstIterator(this, dummyTail);
}


template<class T>
typename List<T>::Iterator List<T>::rbegin() {
	return Iterator(this, dummyTail->previous);
}

template<class T>
typename List<T>::ConstIterator List<T>::rbegin() const {
	return ConstIterator(this, dummyTail->previous);
}

template<class T>
typename List<T>::Iterator List<T>::rend() {
	return Iterator(this, dummyHead);
}

template<class T>
typename List<T>::ConstIterator List<T>::rend() const {
	return ConstIterator(this, dummyHead);
}

template<class T>
void List<T>::clear() {
	for (Node* nodePtr = dummyHead->next; nodePtr != dummyTail; ) {
		Node* currentNodePtr = nodePtr;
		nodePtr = nodePtr->next;
		delete currentNodePtr;
	}
	size = 0;
	dummyHead->next = dummyTail;
	dummyTail->previous = dummyHead;
}

/* List non-member functions */
template<class T>
bool List<T>::operator==(const List<T>& list) const {
	if (size != list.size) {
		return false;
	}

	typename List<T>::ConstIterator elementIterator1 = begin(),
			elementIterator2 = list.begin();
	for (; (elementIterator1 != end())
			&& (elementIterator2 != list.end());
			++elementIterator1, ++elementIterator2) {
		if (*elementIterator1 != *elementIterator2) {
			return false;
		}
	}
	return true;
}

template<class T>
bool List<T>::operator!=(const List<T>& list) const {
	return !(*this == list);
}

template<class T>
void List<T>::copyFrom(const List& sourceList) {
	for (ConstIterator elementIterator = sourceList.rbegin();
			elementIterator != sourceList.rend();
			--elementIterator) {
		insertFirst(*elementIterator);
	}
}

template<class T>
void List<T>::insertFirst(const T& element) {
	Node* previouslyFirstNode = dummyHead->next;
	Node* newNode = new Node(element);
	newNode->previous = dummyHead;
	newNode->next = previouslyFirstNode;
	dummyHead->next = newNode;
	previouslyFirstNode->previous = newNode;
	++size;
}

template<class T>
void List<T>::Iterator::validateListMatch(const List<T>* otherList) const {
	if (list != otherList) {
		throw NonMatchingListException();
	}
}

template<class T>
List<T>::ConstIterator::ConstIterator(const Iterator& iterator) :
	list(iterator.list), current(iterator.current) {}

template<class T>
bool List<T>::Iterator::operator==(const typename List<T>::Iterator& iterator) {
	if (list != iterator.list) {
		return false;
	}
	return current == iterator.current;
}

template<class T>
bool List<T>::Iterator::operator==(
		const typename List<T>::ConstIterator& iterator) {
	if (list != iterator.list) {
		return false;
	}
	return current == iterator.current;
}

template<class T>
bool List<T>::Iterator::operator!=(
		const typename List<T>::ConstIterator& iterator) {
	return !(*this == iterator);
}

template<class T>
void List<T>::Iterator::removeFromList() {
	/* No need to verify that this iterator does not point to the end of the
	 * list - since list's remove verifies it anyway.
	 */
	list->remove(*this);
}

template<class T>
bool List<T>::ConstIterator::operator==(
		const typename List<T>::ConstIterator& iterator) {
	if (list != iterator.list) {
		return false;
	}
	return current == iterator.current;
}

template<class T>
bool List<T>::Iterator::operator!=(const typename List<T>::Iterator& iterator) {
	return !(*this == iterator);
}

template<class T>
T& List<T>::Iterator::operator*() {
	if ((*this == list->end()) || (*this == list->rend())) {
		throw NoElementException();
	}
	return *(current->element);
}

template<class T>
typename List<T>::Iterator& List<T>::Iterator::operator++() {
	assert(list->end() != *this);
	current = current->next;
	return *this;
}

template<class T>
typename List<T>::Iterator List<T>::Iterator::operator++(int) {
	Iterator iteratorBefore = *this;
	++(*this);
	return iteratorBefore;
}

template<class T>
typename List<T>::Iterator& List<T>::Iterator::operator--() {
	assert(list->rend() != *this);
	current = current->previous;
	return *this;
}

template<class T>
typename List<T>::Iterator List<T>::Iterator::operator--(int) {
	Iterator iteratorBefore = *this;
	--(*this);
	return iteratorBefore;
}

/* List::ConstIterator non-member functions */

template<class T>
bool List<T>::ConstIterator::operator!=(
		const typename List<T>::ConstIterator& iterator) {
	return !(*this == iterator);
}

template<class T>
const T& List<T>::ConstIterator::operator*() {
	if ((*this == list->end()) || (*this == list->rend())) {
		throw NoElementException();
	}
	return *(current->element);
}

template<class T>
typename List<T>::ConstIterator& List<T>::ConstIterator::operator++() {
	assert(list->end() != *this);
	current = current->next;
	return *this;
}

template<class T>
typename List<T>::ConstIterator List<T>::ConstIterator::operator++(int) {
	ConstIterator iteratorBefore = *this;
	++(*this);
	return iteratorBefore;
}

template<class T>
typename List<T>::ConstIterator& List<T>::ConstIterator::operator--() {
	assert(list->rend() != *this);
	current = current->previous;
	return *this;
}

template<class T>
typename List<T>::ConstIterator List<T>::ConstIterator::operator--(int) {
	ConstIterator iteratorBefore = *this;
	--(*this);
	return iteratorBefore;
}

#endif /* NEWLIST_H_ */
